package com.hdu.hot100.graph;

import java.util.LinkedList;
import java.util.Queue;

public class lc994 {
    class Solution {
        public int orangesRotting(int[][] grid)
        {
            int[][] directions = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
            Queue<Node> badOranges = new LinkedList<>();
            int freshCount = 0;
            for (int i = 0; i < grid.length; i++)
            {
                for (int j = 0; j < grid[0].length; j++)
                {
                    if (grid[i][j] == 2)
                    {
                        badOranges.add(new Node(i, j));
                    }
                    if (grid[i][j] == 1)
                    {
                        freshCount++;
                    }
                }
            }
            int bound = 0;
            while (freshCount > 0 && !badOranges.isEmpty())
            {
                int size = badOranges.size();
                bound++;
                for (int i = 0; i < size; i++)
                {
                    Node curOrange = badOranges.poll();
                    int curX = curOrange.x;
                    int curY = curOrange.y;
                    for (int[] direction : directions)
                    {
                        int nextX = curX + direction[0];
                        int nextY = curY + direction[1];
                        if (nextX >= 0 && nextX < grid.length && nextY >= 0 && nextY < grid[0].length && grid[nextX][nextY] == 1)
                        {
                            grid[nextX][nextY] = 2;
                            freshCount--;
                            badOranges.add(new Node(nextX, nextY));
                        }
                    }
                }
            }
            return freshCount == 0 ? bound : -1;
        }

        class Node
        {
            int x;
            int y;

            public Node(int x, int y)
            {
                this.x = x;
                this.y = y;
            }
        }
    }
}
